using System.Collections.Generic;
namespace Algorithms
{
	public class UnionFind<T>
	{
		//private Set<Node<T>> Roots = new Set<Node<T>>();
		private Dictionary<T, Node<T>> Nodes = new Dictionary<T, Node<T>>();

		public Node<T> Union(Node<T> set1, Node<T> set2)
		{
			Node<T> root1 = Find(set1);
			Node<T> root2 = Find(set2);

			if (root1.Rank > root2.Rank)
			{
				root2.Parent = root1;
				//Roots.Remove(root2);
				return root1;
			}
			else
			{
				root1.Parent = root2;
				if (root1.Rank == root2.Rank)
				{
					root2.Rank++;
				}
				//Roots.Remove(root1);
				return root2;
			}
		}

		public Node<T> Union(T set1, T set2)
		{
			Node<T> result = Union(Nodes[set1], Nodes[set2]);
			return result;
		}

		public Node<T> Find(Node<T> element)
		{
			if (element.Parent == element)
			{
				return element;
			}

			Node<T> root = element;
			while (root != root.Parent)
			{
				root = root.Parent;
			}

			Node<T> current = element;
			Node<T> parent = current.Parent;
			while (parent != root)
			{
				current.Parent = root;
				current = parent;
				parent = current.Parent;
			}

			return root;
		}

		public Node<T> Find(T element)
		{
			return Find(Nodes[element]);
		}

		public Node<T> MakeSet(T element)
		{
			Node<T> result = new Node<T>(element);
			//Roots.Add(result);
			Nodes.Add(element, result);
			return result;
		}

		public class Node<TElement>
		{
			public Node(TElement initialValue)
			{
				Value = initialValue;
				Parent = this;
			}

			private Node<TElement> mParent = null;
			public Node<TElement> Parent
			{
				get
				{
					return mParent;
				}
				set
				{
					mParent = value;
				}
			}

			private TElement mValue;
			public TElement Value
			{
				get
				{
					return mValue;
				}
				set
				{
					mValue = value;
				}
			}

			private int mRank = 0;
			public int Rank
			{
				get
				{
					return mRank;
				}
				set
				{
					mRank = value;
				}
			}
		}
	}
}
